Digitale Logik
Wir haben im letzten Thema die Bestandteile eines Prozessors kennengelernt, sowie deren Aufgaben bei der Abarbeitung von Programmen.
Nun schauen wir noch einen Schritt tiefer in die elektronischen Komponenten eines Computers hinein und beschäftigen uns dabei mit logischen Schaltungen.
Wir schauen uns dazu zuerst kurz an, was logische Schaltungen überhaupt sind und wie man diese beschreiben kann. Danach lernst du, selbst kleine Schaltungen zu entwerfen.
Abschliessen werden wir das Kapitel mit dem Design einer Halbaddierer-Schaltung. Solche Schaltungen stecken in modernen Prozessoren und sind für die einfache mathematische Operation der Addition von Zahlen zuständig.
🖥️ Präsentationen: Zu diesem Thema gibt es zwei Diskussions-Decks: Teil 1 – Gatter & Schaltungen und Teil 2 – Rechnen mit Gattern.
1. Schaltungen
Wie du weisst, kann ein Computer grundsätzlich nur mit 2 Zuständen umgehen: 0 und 1. Im Computer werden diese zwei Zustände physikalisch als Strom (1) und kein Strom (0) abgebildet. 💡
Digitale Schaltungen bilden den Grundbaustein für sämtliche Logik in Computern.
Schaltungen aus der echten Welt sind leider oft zu komplex, um sie im Detail anschauen zu können. Wir schauen uns darum für die Übungen vorerst abstrakte Beispiele an.
Eine Schaltung besteht aus einer Verknüpfung der folgenden Dinge:
- Eingänge (einfache Vorstellung: Kabel mit/ohne Strom)
- Ausgänge (einfache Vorstellung: Lampen, die leuchten oder nicht)
- Kabel (Leitungen)
- Logische Operatoren, welche die Funktion der Schaltung bestimmen
Schaltungen werden immer für einen spezifischen Zweck entworfen. Ein sehr einfaches Beispiel zur Veranschaulichung ausserhalb des Computers wäre das Licht in einem Raum. Wenn Strom fliesst (Schalter ist an, Zustand 1), sollen eine oder mehrere Lampen angehen, sonst nicht.
Schaltungen im Computer sind weitaus komplexer und haben viele Schalter (Eingänge) und Lampen, die leuchten sollen oder nicht (Ausgänge).
Merke: Eine digitale Schaltung hat also einen oder mehrere Ein- und Ausgänge. Die Ein- und Ausgänge haben zu jedem Zeitpunkt den Wert 0 (kein Strom) oder 1 (Strom).
Die folgende Schaltung hat zwei Eingänge (A und B) sowie zwei Ausgänge (X und Y):
Die Schaltung (in der roten Box) besteht aus einer Reihe von logischen Operatoren, welche die Funktion der Schaltung ausmachen. Mit Funktion meinen wir hier, welche Kombination von 0/1 bei den Eingängen A und B welche Kombination bei den Ausgängen X und Y ergibt.
Beispiel:
Eingabe: A = 0, B = 1
Ausgabe: X = 1, Y = 02. Wahrheitstabellen
Bevor wir uns die genaue Funktionsweise von Schaltungen anschauen, wollen wir Wahrheitstabellen als Methode zur Beschreibung von Schaltungen kennenlernen.
Jede digitale Schaltung kann durch eine Wahrheitstabelle beschrieben werden. In der Wahrheitstabelle werden für alle möglichen Eingabekombinationen die entsprechenden Ausgabewerte festgehalten.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Die Schaltung, welche in der oben stehenden Tabelle beschrieben wird, hat zwei Eingänge (A und B) und einen Ausgang (Y). Überlege dir kurz, was du anhand der Tabelle über diese Schaltung aussagen kannst. Siehst du eine Verbindung zum Programmierkurs vom letzten Semester?
Tipp: Der Ausgang ist genau dann
1, wenn A oder B (oder beide)1sind. Das erinnert nicht zufällig an dasoraus dem Programmieren.
3. Ein- und Ausgänge
In den kommenden Aufgaben werden wir eigene kleine Schaltungen entwerfen. Dafür benötigen wir einfache Ein- und Ausgabemöglichkeiten.
Als Eingang dient ein Schalter, der entweder 0 (kein Strom) oder 1 (Strom) liefert. Als Ausgang dient eine Lampe, die leuchtet (1) oder dunkel bleibt (0):
4. Aufbau von Schaltungen
4.1 Verbindungen
Wir lernen nun verschiedene logische Bauteile von Schaltungen kennen. Eine Schaltung ist lediglich eine Verknüpfung von Eingaben, Ausgaben und logischen Bauteilen.
Die einfachste Schaltung ist eine direkte Verbindung von Ein- und Ausgabe:
Eine Verbindung (Leitung) kann auch verzweigt werden. Die Verzweigung wird durch einen kleinen Kreis (Punkt) markiert:
Hinweis: Die beiden neuen Leitungen übertragen immer denselben Wert wie die Leitung, die verzweigt wurde. Um Leitungen zusammenzuführen, brauchen wir aber logische Bauteile, sogenannte Operatoren (auch Gatter genannt).
4.2 Operatoren (Gatter)
Wir schauen uns jetzt die wichtigsten Gatter an. Am besten probierst du gleich jedes davon im folgenden Simulator aus: Wähle oben ein Gatter, tippe die Schalter A und B an und beobachte, wann die Lampe am Ausgang leuchtet. Die aktuelle Zeile der Wahrheitstabelle wird jeweils hervorgehoben.
Tippe auf die Schalter (A, B), um die Eingänge umzustellen.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Das AND-Gatter liefert nur dann 1, wenn beide Eingänge 1 sind.
Unten findest du zu jedem Gatter zusätzlich die Wahrheitstabelle als Nachschlage-Referenz.
4.2.1 Inverter
Ein Inverter ist ein Operator mit einem Eingang. Der Ausgang hat den Wert 1, wenn der Eingang 0 hat, und umgekehrt. Das Signal wird also invertiert.
| A | Y |
|---|---|
| 0 | 1 |
| 1 | 0 |
Beispiel: Das Licht im Kühlschrank geht an, sobald die Türe nicht mehr auf den Knopf drückt. Der Türknopf ist der Eingang, das Licht der Ausgang – dazwischen liegt ein Inverter.
4.2.2 AND-Gatter
Das AND-Gatter hat zwei Eingänge und einen Ausgang. Der Ausgang hat nur dann den Wert 1, wenn beide Eingänge 1 sind.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Beispiel: In einer Kaffeemaschine wird der Motor für die Mühle aus Sicherheitsgründen nur dann aktiviert, wenn gleichzeitig der Deckel geschlossen und der Stromschalter aktiviert ist.
4.2.3 OR-Gatter
Beim OR-Gatter hat der Ausgang den Wert 1, wenn mindestens einer der Eingänge 1 ist.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Beispiel: In einem Haus soll die Eingangstüre sowohl aus der Wohnung im ersten Stock als auch aus der Wohnung im zweiten Stock per Knopf geöffnet werden können.
4.2.4 XOR-Gatter
Beim XOR-Gatter (englisch Exclusive OR) hat der Ausgang den Wert 1, wenn entweder A oder B 1 ist – aber nicht, wenn beide 1 sind.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
4.2.5 NAND-Gatter
Das letzte Gatter, das wir uns anschauen, ist das NAND-Gatter. Der Name steht kurz für Not-AND; es ist einfach die Kombination eines AND-Gatters und eines Inverters. Der Ausgang ist also genau das Gegenteil vom AND.
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Hinweis: Das NAND-Gatter hat eine besondere Bedeutung unter den logischen Gattern. Man kann beweisen, dass sich jede beliebige logische Schaltung ausschliesslich aus NAND-Gattern aufbauen lässt (diese Eigenschaft nennt man funktionale Vollständigkeit; nachgewiesen wurde sie 1913 vom Logiker Henry Sheffer, weshalb das NAND auch «Sheffer-Strich» heisst). Da NAND-Gatter zudem physikalisch besonders einfach herzustellen sind, bestehen moderne Prozessoren (und andere Chips) zu einem grossen Teil aus NAND-Gattern.
4.3 Selbsttest: Gatter erkennen
Erkennst du ein Gatter an seiner Wahrheitstabelle? Probier es aus:
Welches Gatter ist das?
Richtig: 0 / 0Zu welchem Gatter gehört diese Wahrheitstabelle?
| A | Y |
|---|---|
| 0 | 1 |
| 1 | 0 |
4.4 Halbaddierer & Binäre Addition
Weiter oben wurde bereits erwähnt, dass alle mathematischen Operationen im Computer mit relativ einfachen (und manchmal auch sehr komplexen) Schaltungen durchgeführt werden. Im Folgenden schauen wir uns dies am einfachsten Beispiel an: der Addition.
Binäre Addition
Die Addition von zwei Binärzahlen funktioniert ganz ähnlich wie die schriftliche Addition von zwei Dezimalzahlen – nur, dass wir bereits bei 1 + 1 einen Übertrag erhalten. Es gelten diese vier Grundregeln:
| Rechnung | Ergebnis | Bedeutung |
|---|---|---|
0 + 0 | 0 | kein Übertrag |
0 + 1 | 1 | kein Übertrag |
1 + 0 | 1 | kein Übertrag |
1 + 1 | 10 | Ergebnis 0, Übertrag 1 |
Genau wie im Dezimalsystem rechnen wir Stelle für Stelle von rechts nach links und schleppen den Übertrag mit. Ein Beispiel – wir addieren
1 1 ← Überträge
1 0 1 1 (11)
+ 0 1 1 0 (6)
---------
1 0 0 0 1 (17)Das Ergebnis
Wer die schriftliche binäre Addition nochmals in Ruhe erklärt haben möchte, findet hier ein gutes Video.
4.4.1 Der Halbaddierer
Ein Halbaddierer ist eine Schaltung, welche zwei einstellige Binärzahlen addieren kann. Er muss also genau die vier Rechnungen aus der Tabelle oben lösen können.
Die Schaltung benötigt 2 Eingänge (für die beiden Summanden A und B) und 2 Ausgänge: einen für die Einer-Stelle des Resultats und einen für die Zweier-Stelle (den Übertrag).
Die Wahrheitstabelle sieht so aus:
| A | B | Zweier | Einer |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Schaut man die beiden Ausgabespalten einzeln an, erkennt man zwei alte Bekannte:
- Die Einer-Spalte entspricht genau einem XOR-Gatter (1, wenn genau einer der Eingänge 1 ist).
- Die Zweier-Spalte (der Übertrag) entspricht genau einem AND-Gatter (1, nur wenn beide Eingänge 1 sind).
Die Idee des Halbaddierers ist also: Der Wert der Einer-Stelle wird durch ein XOR-Gatter berechnet, der Übertrag (Zweier-Stelle) durch ein AND-Gatter. Probier die Schaltung unten aus (Modus Halbaddierer):
Tippe auf die Schalter, um die Eingänge umzustellen.
4.4.2 Der Volladdierer
Ein Halbaddierer addiert, wie wir gesehen haben, zwei Bits und liefert das Resultat der Einer-Stelle und den Übertrag auf die Zweier-Stelle.
Aus unserem Halbaddierer können wir nun fast einen vollwertigen Addierer basteln. Wir haben aber noch ein Problem: Unser Halbaddierer berücksichtigt jeweils nur die beiden Summanden und nicht den Übertrag aus der vorherigen Stelle.
Wenn zwei mehrstellige Binärzahlen addiert werden sollen, muss dieser Übertrag mitgerechnet werden. Ab der zweiten Stelle passiert an jeder Stelle Folgendes:
- Die beiden Ziffern an der aktuellen Stelle werden addiert.
- Zum Zwischenresultat wird der Übertrag der vorherigen Stelle addiert.
- Das Resultat wird gespeichert, und der neue Übertrag wird an die nächste Stelle weitergegeben.
Genau das leistet der Volladdierer. Er besteht aus zwei Halbaddierern und einem OR-Gatter für den Übertrag: Der erste Halbaddierer addiert A und B, der zweite addiert dazu den hereinkommenden Übertrag Cin. Ein Übertrag entsteht dabei, wenn einer der beiden Halbaddierer einen Übertrag meldet – dafür sorgt das OR-Gatter.
Schalte den Simulator oben in den Modus Volladdierer und probiere z.B. 1 + 1 + 1 aus (alle drei Schalter auf 1): Das Ergebnis muss 112 sein – Summe 1, Übertrag 1.
5. Schaltungen selbst bauen
Jetzt bist du dran: Lies die Aufgabe, fülle die Wahrheitstabelle aus und baue die passende Schaltung. Füge Gatter über die Palette hinzu, verschiebe sie mit der Maus (oder dem Finger) und verbinde sie, indem du einen Ausgang und danach einen Eingang antippst. Mit den Eingangs-Schaltern kannst du deine Schaltung testen, bevor du auf Prüfen klickst.
Aufgabe 1 – Direkte Verbindung
Zum Aufwärmen: Verbinde den Eingang A direkt mit dem Ausgang Y. Der Ausgang soll immer denselben Wert haben wie der Eingang – ganz ohne Gatter. Tippe dazu den Ausgangs-Punkt (○) von A an und danach den Eingangs-Punkt (○) von Y.
| A | Y |
|---|---|
| 0 | · |
| 1 | · |
6. Quiz
Digitale Logik – teste dein Wissen
Frage 1 von 6
7. Aufgaben
Aufgabe 1 – Wahrheitstabelle aufstellen
Stelle die Wahrheitstabelle für ein NOR-Gatter auf. Ein NOR-Gatter ist ein OR-Gatter mit nachgeschaltetem Inverter (also Not-OR).
Lösung anzeigen
Zuerst das OR bestimmen, dann jeden Ausgang invertieren:
| A | B | OR | NOR (= invertiert) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Das NOR-Gatter liefert also nur dann 1, wenn beide Eingänge 0 sind.
Aufgabe 2 – Welches Gatter passt?
Eine Schaltung mit zwei Eingängen liefert die folgende Wahrheitstabelle. Um welches Gatter handelt es sich?
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Lösung anzeigen
Der Ausgang ist nur dann 0, wenn beide Eingänge 1 sind – sonst immer 1. Das ist genau das Verhalten eines NAND-Gatters.
Aufgabe 3 – Halbaddierer nachvollziehen
Du gibst einem Halbaddierer die Eingänge A = 1 und B = 1. Welche Werte haben die Ausgänge Einer und Zweier, und welche Rechnung stellt das dar?
Lösung anzeigen
- Einer (XOR):
1 XOR 1 = 0 - Zweier (AND):
1 AND 1 = 1
Zusammengesetzt ergibt das die Binärzahl 102, also die Rechnung 1 + 1 = 2. Der Übertrag (Zweier) ist 1, die Einer-Stelle 0. ✓
8. Quellen
Viele der Inhalte, Aufgaben und Grafiken wurden in angepasster Form von den Inhalten der Kolleg:innen des Gymnasium Kirchenfelds übernommen.